package leetcode.other.sort;


import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * @Description: https://leetcode.cn/problems/smallest-k-lcci/description/
 * @Author Ammar
 * @Create 2023/9/14 19:20
 */
public class _面试题_17_14_最小K个数 {
    public int[] smallestK(int[] arr, int k) {
        int[] res = new int[k];
        if (k == 0) return res;
        // 小顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        for (int i = 0; i < k; i++) {
            queue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll();
        }
        return res;
    }
    public int[] smallestK1(int[] arr, int k) {
        quickSelect(arr, 0, arr.length - 1, k);
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    private void quickSelect(int[] arr, int left, int right, int k) {
        if (left >= right) return;
        int pos = patition(arr, left, right);
        int num = pos - left + 1;
        if (k == num) return;
        else if (k < num) {
            quickSelect(arr, left, pos, k);
        } else {
            quickSelect(arr, pos + 1, right, k - num);
        }
    }

    private int patition(int[] nums, int left, int right) {
        int pivotIndex = left + new Random().nextInt(right - left);
        int pivot = nums[pivotIndex];
        swap(nums, right, pivotIndex);
        int storeIndex = left;
        for (int i = left; i <= right; i++) {
            if (nums[i] < pivot) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        swap(nums, storeIndex, right);
        return storeIndex;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
